package com.lx.algorithm.code.xly3.class03;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-04 16:25:26
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-04     张李鑫                     1.0         1.0 Version
 */
public class Code02 {
    /**
     * 背包容量为w
     * 一共有n袋零食, 第i袋零食体积为v[i]
     * 总体积不超过背包容量的情况下，
     * 一共有多少种零食放法？(总体积为0也算一种放法)。
     */

    public static int bag(int w, int[] v) {
        return process(w, v, 0);
    }

    private static int process(int w, int[] v, int i) {
        if (i == v.length) {
            return w < 0 ? 0 : 1;
        }
        int next = 0;

        if (w - v[i] >= 0) {
            next += process(w - v[i], v, i + 1);
        }
        return next + process(w, v, i + 1);
    }

    public static int dp(int w, int[] v) {
        int[][] dp = new int[v.length + 1][w + 1];
        for (int i = 0; i <= w; i++) {
            dp[v.length][i] = 1;
        }
        for (int i = dp.length - 2; i >= 0; i--) {
            for (int i1 = dp[i].length - 1; i1 >= 0; i1--) {
                int next = 0;
                if (i1 - v[i] >= 0) {
                    next += dp[i + 1][i1 - v[i]];
                }
                dp[i][i1] = next + dp[i + 1][i1];
            }
        }

        return dp[0][w];
    }

    public static int ways3(int[] arr, int w) {
        int N = arr.length;
        int[][] dp = new int[N][w + 1];
        for (int i = 0; i < N; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= w) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= w; j++) {
                dp[i][j] = dp[i - 1][j] + ((j - arr[i]) >= 0 ? dp[i - 1][j - arr[i]] : 0);
            }
        }
        int ans = 0;
        for (int j = 0; j <= w; j++) {
            ans += dp[N - 1][j];
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 9, 9, 1, 4, 3, 22,31,15,12,52,12};
        int w = 96;
        System.out.println(bag(w, arr));
        System.out.println(dp(w, arr));
        System.out.println(ways3(arr, w));
    }
}
